class LinkNode<E>{
    E data;
    LinkNode<E> next;
    LinkNode<E> prev;
    public LinkNode() {
        data = (E)new Object();
        next = null;
        prev = null;
    }
    public LinkNode(E data) {
        this.data = data;
        next = null;
        prev = null;
    }
}
public class LinkQueue<E> {
    LinkNode<E> head;
    public LinkQueue() {
        head = new LinkNode<E>();
        head.next = head;
        head.prev = head;
    }
    public boolean empty(){
        return head.next==head;
    }
    public void push(E e){
        LinkNode<E> newnode = new LinkNode<E>(e);
        newnode.next = head;
        head.prev.next = newnode;
        newnode.prev = head.prev;
        head.prev = newnode;
    }
    public E pop(){
        if(empty()){
            throw new IllegalArgumentException("队列空");
        }else{
            E ret = head.next.data;
            head.next = head.next.next;
            head.next.prev = head;
            return ret;
        }
    }
    public E top(){
        if(empty()) {
            throw new IllegalArgumentException("队列空");
        }else {
            return head.prev.data;
        }
    }
}
